// 给定一个可包含重复数字的序列，返回所有不重复的全排列。

// 示例:

// 输入: [1,1,2]
// 输出:
// [
//   [1,1,2],
//   [1,2,1],
//   [2,1,1]
// ]

#include <vector>
#include <set>
using namespace std;

/* 回溯 set去重
*/
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> res{};
        dfs(0, nums, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
    void dfs(int start, vector<int>& nums, set<vector<int>>& res) {
        if (start == nums.size()) {
            res.insert(nums);
            return;
        }
        for (int i{start}; i < nums.size(); ++i) {
            swap(nums[i], nums[start]);
            dfs(start + 1, nums, res);
            swap(nums[i], nums[start]);
        }
    }
};

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res{};
        int n = nums.size();
        vector<bool> visited(n, false);
        vector<int> temp{};
        sort(nums.begin(), nums.end());
        dfs(0, n, nums, visited, temp, res);
        return res;
    }
    void dfs(int start, int n, vector<int>& nums, vector<bool>& visited, vector<int>& temp, vector<vector<int>>& res) {
        if (start == n) {
            res.emplace_back(temp);
            return;
        }
        for (int i{0}; i < n; ++i) {
            if (visited[i] == true || (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false)) {
                continue;
            }
            temp.emplace_back(nums[i]);
            visited[i] = true;
            dfs(start + 1, n, nums, visited, temp, res);
            visited[i] = false;
            temp.pop_back();
        }
    }
};